package midalgorithms.list;

public class _02OddEvenList {
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //  尝试递归
        ListNode even = findOdd(head.next);
        ListNode odd = findOdd(head);
        //  其实这里的end在递归里重复算了很多次，也可以单独拿出来计算end的值
        //end.next = even;
        ListNode end = findEnd(odd);
        end.next = even;
        return odd;
    }

    private static ListNode findEnd(ListNode odd) {
        if (odd.next == null){
            return odd;
        }
        return findEnd(odd.next);
    }

    //static ListNode end = new ListNode();
    private static ListNode findOdd(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode newList = new ListNode(head.val);
        newList.next = findOdd(head.next.next);
        /**
        if (newList.next == null || newList.next.next == null){
            end = newList.next == null ? newList : newList.next;
        }
        */
        return newList;
    }
}
